1. Field of the Invention
This invention is related to the field of error detection and correction codes.
2. Description of the Related Art
Error codes are commonly used in electronic systems to detect and correct data errors, such as transmission errors or storage errors. For example, error codes are used to detect and correct errors in data transmitted via any transmission medium (e.g. conductors and/or transmitting devices between chips in an electronic system, a network connect, a telephone line, a radio transmitter, etc.). Error codes are also used to detect and correct errors associated with data stored in the memory of computer systems. In such systems, error correction bits, or check bits, may be generated for the data prior to its transfer or storage. When the data is received or retrieved, the check bits may be used to detect and correct errors within the data.
Device failures are a common source of error in electrical systems. Faulty devices can include faulty memory chips or faulty data paths provided between devices of a system. Faulty data paths can result from, for example, faulty pins, faulty data traces, or faulty wires. Additionally, memory modules, which often contain multiple memory chips, can fail. Circuitry which drives the data paths can also fail.
Another source of error in electrical systems are so-called “soft” or “transient errors”. A transient memory error is caused by the occurrence of an event, rather than a defect in the memory/transmission circuitry itself. Transient memory errors can occur due to, for example, random alpha particles striking the memory circuit. Transient communication errors can occur due to noise on the data paths, inaccurate sampling of the data due to clock drift, etc. On the other hand, “hard” or “persistent” errors occur due to device failure.
Generally, various error detection code (EDC) and error correction code (ECC) schemes are used to detect and correct memory and/or communication errors. For example, parity can be used. With parity, a single parity bit is stored/transmitted for a given set of data bits, representing whether the number of binary ones in the data bits is even or odd. The parity is generated when the set of data bits is stored/transmitted and is checked when the set of data bits is accessed/received. If the parity doesn't match the accessed set of data bits, then an error is detected.
Other EDC/ECC schemes assign several check bits per set of data bits. In a typical code (e.g. a Hamming code or related code types), the check bits are encoded from various overlapping combinations of the corresponding data bits. The encodings are selected such that a bit error or errors can be detected, and in some cases the encodings are selected such that the bit or bits in error are identifiable so that the error can be corrected (depending on the number of bits in error and the scheme being used). Another EDC scheme is a cyclic redundancy code (CRC) scheme. With a typical CRC scheme, errors in the data can be detected but not corrected. Typically, as the number of bit errors that can be detected and/or corrected increases, the number of check bits used in the scheme increases as well.